#include "dat.h"

using namespace std; 

const int FLOW_N = 1000, FLOW_M = 100000, FLOW_INF = 0x3f3f3f3f; 

struct Flow {
    //最大费用流, 于二分图最大权匹配
    int h[FLOW_N], val[FLOW_M], ne[FLOW_M], cf[FLOW_M], idx; 
    double w[FLOW_M], dist[FLOW_N];
    int n, m, S = FLOW_N - 1, T = FLOW_N - 2; 
    int que[FLOW_N], incf[FLOW_N], pre[FLOW_N]; 
    bool st[FLOW_N]; 

    void add(int a, int b, int c, double d) {
        val[idx] = b, ne[idx] = h[a], cf[idx] = c, w[idx] = d, h[a] = idx ++ ; 
        val[idx] = a, ne[idx] = h[b], cf[idx] = 0, w[idx] = -d, h[b] = idx ++ ;
    }

    void clear() {
        memset(h, -1, sizeof(h)); 
        idx = 0; 
    }

    double get_gain(Robot *rob, vector<SingleAction>::iterator act) {
        //先暂定为 gain / time 
        int t = act->time + calculateTimeBetweenLoc(workbench_list[act->workbench_start].loc, rob->loc);
        return 1.0 * act->gain; 
    }

    bool spfa() {
        for (int i = 0; i < FLOW_N; i ++ )
            dist[i] = -1e20; 
        incf[T] = 0; 
        int head = 0, tail = 0; 
        que[tail ++ ] = S, incf[S] = FLOW_INF, dist[S] = 0; 
        while (head != tail) { //循环队列
            int t = que[head ++ ]; 
            if (head == FLOW_N) head = 0; 
            st[t] = false; 
            for (int i = h[t]; ~i; i = ne[i]) {
                int j = val[i]; 
                if (cf[i] && (dist[j] < dist[t] + w[i])) {
                    dist[j] = dist[t] + w[i]; 
                    incf[j] = min(incf[t], cf[i]); 
                    pre[j] = i; 
                    if (!st[j]) {
                        que[tail ++ ] = j; 
                        if (tail == FLOW_N) tail = 0; 
                        st[j] = true; 
                    }
                }
            }
        }
        return incf[T] > 0; 
    }

    void EK() {
        //最大费用流, 这里省掉了结果, 只需要知道具体的分配情况
        while ((spfa())) {
            int t = incf[T]; 
            for (int i = T; i != S; i = val[pre[i] ^ 1])
                cf[pre[i]] -= t, cf[pre[i] ^ 1] += t; 
        }
    }

    vector<pair<int, int>> solve(vector<Robot*> &rob, vector<vector<SingleAction>::iterator> &act) {
        /***********建图***********/
        clear(); //重置图
        n = rob.size(); // X 部集编号 : [1, n]
        m = act.size(); // Y 部集编号 : [n + 1, n + m]
        for (int i = 1; i <= n; i ++ ) //源
            add(S, i, 1, 0);
        for (int i = 1; i <= m; i ++ ) //汇
            add(i + n, T, 1, 0); 
        //X 部集 -> Y 部集
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                double gain = get_gain(rob[i - 1], act[j - 1]); //机器人执行任务的收益
                add(i, j + n, 1, gain); 
            }
        /***********求解***********/
        EK(); 
        /********返回分配信息*******/
        vector<pair<int, int>> ans; 
        for (int i = 0; i < idx; i += 2) {
            if (cf[i] == 0 && w[i] != 0) { //在最终的边匹配中, 且不涉及源汇
                ans.push_back({val[i ^ 1] - 1, val[i] - n - 1}); 
            }
            cf[i] += cf[i ^ 1], cf[i ^ 1] = 0; //回流
        }
        return ans; 
    }
}flow;

void assainTaskForRobots(vector<Robot*> &rob)
{
    filterAvailableAction();
    if(available_action.empty())
        return;
    vector<pair<int, int>> r = flow.solve(rob, available_action);
    for(auto i : r)
    {
        rob[i.first]->cur_action = available_action[i.second];
        rob[i.first]->expect_loc = workbench_list[available_action[i.second]->workbench_start].loc;
        cerr << "Debug:" << i.first << " ->" << i.second << ' ' << available_action[i.second]->workbench_start << ' ' << available_action[i.second]->workbench_end << '\n';
    }
}